package leetcode;

import java.util.Arrays;

public class _0016 {
    /**
     * 最接近的三数之和
     */
    class Solution {
        public int threeSumClosest(int[] nums, int target) {
            Arrays.sort(nums);
            int n = nums.length;
            int best = 10000000;
            for(int i=0;i<n-1;i++){
                int x = nums[i];
                if(i>0&&nums[i]==nums[i-1]){
                    continue;
                }
                int j=i+1;
                int k=n-1;
                while(j<k){
                    int sum = x+nums[j]+nums[k];
                    if(sum==target){
                        return target;
                    }
                    if(Math.abs(sum-target)<Math.abs(best-target)){
                        best = sum;
                    }
                    if(sum-target>0){
                        k--;
                        while(k>j&&nums[k]==nums[k+1]){
                            k--;
                        }
                    }else{
                        j++;
                        while(j<k&&nums[j]==nums[j-1]){
                            j++;
                        }
                    }
                }
            }
            return best;
        }
    }
}
